1. Field of the Invention
This invention relates to digital gate circuits, specifically to gate circuits that are adapted to accept a bit stream containing sequences of incoming bytes or datum segments that may have varying bit lengths, and further to a method of encoding such datum segments that includes specifying the bit length.
2. Background Information
In early commercial implementations of digital circuit technology, one principal operative datum other than the bit itself was the 4-bit “byte,” selected both because it was of a size for which circuitry could be fabricated by the level of manufacturing technology then available, and because 4 was an integral power of 2 for purposes of convenient encoding and the future growth of chip sizes “M,” following the pattern M=2n, where n=2, 3, 4, . . . , and hence the series of possible “byte” or “word” sizes became 4, 8, 16, . . . . Except in connection with video transmissions, and in data compression as in Huffman coding, there has been little or no development of any digital data processing systems that are capable of operating on digital “bytes” of varying length. Those kinds of procedures have been adapted to the particular circumstances of those cases, but perhaps because of that standardization of chip sizes, do not provide any truly general method of handling variable length “bytes.”
The number of distinct entries (e.g., addresses) obtainable from the different byte sizes indicated above is also given by M, e.g., a 12 bit byte yields 212=4096=4K memory locations. A sequence of 8 bits sufficed to encode the English alphabet, the ten Arabic digits, and a number of non-printing characters and a parity bit in ASCII code. Use of the 8-bit byte became standard and was employed in a wide range of applications, including the Internet and other communications. In that scheme, the term “byte” meant an 8-bit sequence, and longer bit sequences comprised “words” having the capacity for some number of 8-bit bytes, e.g., 2 bytes in a 16 bit word, 4 bytes in a 32 bit word, etc.
While that scheme accommodates substantial computing power, as the path sizes becoming available have increased to 64 or more, systems so constructed also become more wasteful. Many computer operations do not require very large words or bytes, and can be carried out using standard 8-bit bytes which, if operating in a 32-bit bus and CPU system, would leave 24 bits unused with each data transfer. If one sends an 8-bit byte over a 128-bit line one has effectively “wasted” 120 locations—fifteen 8-bit bytes—that might have been used otherwise. The concatenator of U.S. Pat. No. 6,208,275 issued Mar. 27, 2001, to the present inventor helps to eliminate that kind of loss by, for example, permitting concatenation of four 8-bit bytes prior to entry into the 32-bit system, or sixteen 8-bit bytes on a 128-bit line. A single addressing and READ cycle to acquire an instruction, or an addressing and WRITE cycle to record a result, will transfer 32 information bits instead of requiring four cycles (8 bits at a time).
To carry out numerical calculations the use of larger datum segment sizes becomes essential. Any large number can be expressed as the product of an argument and a “power of ten,” but numbers such as pi (μ) or epsilon (ε) may need expression at very high resolution, i.e., by a number of significant figures that exceeds the capacity of the 8-bit byte. In attempting to carry out high precision calculations, indeed, it is very disruptive suddenly to encounter an exponential expression of a number. Even a 16-bit byte can express numbers in normal binary code only up to 5 significant figures as 65,535. To include both positive and negative numbers one bit is used to express the sign, hence a 16-bit byte can express numbers only to +/−32,768, or, in general, the number expression range Rn of a byte of size n is given by Rn=+/−2(n−1). For a 32-bit byte R32=+/−231=+/−2,147,483,648, while for a 64-bit byte the range is given by R64=+/−263=+/−9,223,372,036,854,775,808.
There may also be operations that could be accommodated using words of other sizes than those that can be described by the standard formula M=2n or, through use of a concatenator and a data enumerator, integral multiples thereof. When those patents state that appropriate instances of the device can provide bytes having bit lengths of “any” size, e.g., 7 bits, 9 bits, etc., in the case of prime numbers in particular that could be done only by using 1-bit “bytes” to be concatenated together, i.e., when the device would have been constructed to act as a serial-to-parallel converter. Moreover, once such a word size had been selected, all of the data must be expressed in bytes of the same size. Lesser bit count data paths tend towards less waste of unused bit locations, but limit the range of data that can be treated, while the use of larger data paths that can express any range of data desired will tend towards more waste of digital space. Through this invention, however, both horns of that dilemma are almost entirely eliminated, by a system that accommodates “bytes” of variable length. Waste of digital space is virtually eliminated, while at the same time data that require large byte sizes to be expressed can be treated. Remnant amounts of wasted digital space arise only because the data treated does not add up exactly to the size of the available data path or register.
When treating text, the apparatus described in the '275 and '378 patents serves less well to eliminate wasted bus or ALU register space. The word “place,” for example, can be expressed in ASCII code as five 8-bit bytes, or as a 40-bit word when excluding start and stop bits, but a system wherein word sizes are defined by M=2n is not adapted to treat words of that size in one piece as would be desired. Even a 32-bit bus is too small, and 64, the next larger size available under the M=2n formula, if transmitting the word “place” in ASCII code would leave 24 bits of wasted space.
Also, there may be operations that could be carried out in a 16-bit system with “perfect fit” as by having two 8-bit bytes, but other data at hand might have been expressible in code of varying sizes as, say, first a 4-bit byte and then a 12-bit byte. The operation in that case would require the use of two transmissions in a 16-bit system, unless there were some way of concatenating bytes of differing size, which the apparatus of the '275 and '378 patents cannot do. Thus, while that apparatus is very useful as to ASCII-encoded data or to any other system that had been designed to treat only bytes of a fixed size, that apparatus does not entirely eliminate the occurrence of wasted bus and ALU register space. Applicant is not aware of any case in which codes adapted to express the lengths of variable length bit sequences other than through varying numbers of bytes of a fixed size have been suggested, or variable length gates have been shown, applied, or even suggested to apply, for the purpose of reducing wastage of bit space in data processing systems.
Nearly complete resolution of that issue would be achieved in a system that accommodated words of varying size whereby in principle, except for the occasional collection of just a few “left over” bit locations, every bus or register location could be used in its entirety. The internet well illustrates that a number of problems would arise if byte sizes were allowed to vary. In order to identify those problems it is necessary to take note of the START and STOP bits. That method of delineating a byte of fixed size cannot be applied when the byte size is allowed to vary, since the location of the START and STOP bits would not be known. Some other means of delineating that byte size must be found.
Besides improving data transmission efficiency by zero stripping, the invention is also intended to encompass the transmission of numerical data in normal binary code wherein, e.g., 123 is transmitted not in ASCII code as “123” that requires three 8-bit bytes, but in normal binary code as 1111011. An advantage in so doing is that the number itself can be transmitted in 7 bits, or 8 if parity were used, or 10 counting START and STOP bits, rather than the 30 bits that would be required to transmit “123” in ASCII code (with START and STOP bits). (As will be seen below, additional “control code” is also required.) At the same time, it would be quite wasteful, for example, to have to express the number 2 by the complete binary code 00000010 in an 8-bit binary code, since only 2 bits would suffice. If it were not known that the bit sequence had only 8-bit bytes in it, however, there would be no way to detect whether a 10th bit (as a “1” bit) was a STOP bit, was the last position of a 9-bit byte, or was another bit of a byte of some yet larger and unknown size. In fact, any earlier “1” bit might have been intended as a STOP bit in a byte of some size less then 8 bits. A system that treats bytes of variable length thus requires some unambiguous means, other than by position or a single bit, of establishing the size of each byte.
Variable length bytes can also be used for purposes other than communications, as in a computer, thereby to save memory and circuitry usage. That could not be accomplished unless there were variable gates and the like available within the computer. In any event, variable length gates must be used in order to form variable length bytes. The invention thus provides hardware that is centered around the variable length gates that are essential to the zero stripping process, encoding systems that can express the full meaning of varying length datum segments, hardware means for interpreting those encoding systems, and addressing methods for the reception, storage, and access to such data.